Thuật toán cho hai chuỗi Bài toán chuỗi con chung dài nhất

Bài toán LCS có một cấu trúc con tối ưu: Có nghĩa là bài toán có thể được chia thành các bài toán con nhỏ hơn và đơn giản hơn, và các chính bài toán con cũng được chia thành các bài toán con đơn giản hơn, và cứ thế, cho đến khi, cuối cùng, nghiệm của bài toán trở nên đơn giản và dễ nhận thấy. LCS nói riêng có các bài toán con chồng chéo: các nghiệm cho các bài toán con cấp cao sẽ sử dụng lại các nghiệm cho các bài toán con cấp thấp hơn. Các vấn đề với hai thuộc tính này có thể giải quyết được bằng quy hoạch động, trong đó các nghiệm của bài toán con sẽ được lưu lại để xử lý lúc sau.

Tiền tố

Ta định nghĩa tiền tố Sn của S là chuỗi chứa n ký tự đầu tiên của S. [2] Ví dụ: các tiền tố của S = (AGCA) là

S0 = ()S1 = (A)S2 = (AG)S3 = (AGC)S4 = (AGCA).

Gọi LCS(X, Y) là một hàm tính toán chuỗi con chung dài nhất cho X và Y. Một hàm như vậy có hai tính chất đặc biệt như sau:

Tính chất đầu tiên

LCS(X^A, Y^A) = LCS (X, Y)^A, cho tất cả các chuỗi X, Y và tất cả các ký hiệu A, trong đó dấu ^ biểu thị phép nối xâu. Điều này cho phép chúng ta đơn giản hóa việc tính toán LCS cho hai chuỗi kết thúc cùng một ký hiệu. Ví dụ: LCS ("BANANA", "ATANA") = LCS ("BANAN", "ATAN") ^ "A", Tiếp tục cho các ký hiệu chung còn lại, LCS ("BANANA", "ATANA") = LCS (" BAN "," AT ") ^" ANA".

Tính chất thứ hai

Nếu A và B là hai ký hiệu riêng biệt (A≠B), thì LCS (X^A, Y^B) là một trong hai xâu có độ dài cực đại trong tập {LCS(X^A, Y), LCS(X, Y^B)}, cho tất cả các xâu X và Y.

Ví dụ: LCS ("ABCDEFG", "BCDGK") là xâu dài hơn của LCS ("ABCDEFG", "BCDG") và LCS ("ABCDEF", "BCDGK"); nếu cả hai có độ dài bằng nhau, ta có thể chọn tùy ý một trong những chuỗi thỏa mãn.

Định nghĩa hàm LCS

Cho hai chuỗi được xác định như sau: X = ( x 1 x 2 ⋯ x m ) {\displaystyle X=(x_{1}x_{2}\cdots x_{m})} và Y = ( y 1 y 2 ⋯ y n ) {\displaystyle Y=(y_{1}y_{2}\cdots y_{n})} . Các tiền tố của X {\displaystyle X} là X 1 , 2 , … , m {\displaystyle X_{1,2,\dots ,m}} ; tiền tố của Y {\displaystyle Y} là Y 1 , 2 , … , n {\displaystyle Y_{1,2,\dots ,n}} . Gọi L C S ( X i , Y j ) {\displaystyle {\mathit {LCS}}(X_{i},Y_{j})} là đại diện cho tập hợp các chuỗi con chung dài nhất cho các tiền tố của X i {\displaystyle X_{i}} và Y j {\displaystyle Y_{j}} . Tập hợp các chuỗi này được định nghĩa như sau.

L C S ( X i , Y j ) = { ∅ if i = 0 or j = 0 L C S ( X i − 1 , Y j − 1 ) ^ x i if i , j > 0 and x i = y j max ⁡ { L C S ( X i , Y j − 1 ) , L C S ( X i − 1 , Y j ) } if i , j > 0 and x i ≠ y j . {\displaystyle {\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\emptyset &{\mbox{if }}i=0{\mbox{ or }}j=0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\hat {}}x_{i}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}=y_{j}\\\operatorname {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS}}(X_{i-1},Y_{j})\}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}\neq y_{j}.\end{cases}}}

Làm việc với ví dụ

Để lấy ví dụ, ta sẽ tìm chuỗi con dài nhất chung cho hai xâu R = (GAC) và C = (AGCAT). Vì hàm LCS xét từ vị trí 0, nên để thuận tiện, ta sẽ xác định các tiền tố 0 là trống cho các chuỗi này: R0 = Ø; và C0 = Ø. Tất cả các tiền tố được đặt trong một bảng với C ở hàng đầu tiên và R ở cột đầu tiên:

Chuỗi LCS
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø
A	Ø
C	Ø

Bảng này được sử dụng để lưu trữ trình tự tính LCS cho mỗi bước tính toán. Cột thứ hai và hàng thứ hai đã được điền bằng Ø, bởi vì khi một chuỗi trống được so sánh với một chuỗi không trống, chuỗi con chung dài nhất luôn là chuỗi trống.

LCS (R1, C1) được xác định bằng cách so sánh các phần tử đầu tiên trong mỗi chuỗi. G và A không giống nhau, vì vậy LCS này nhận (sử dụng tính chất thứ hai trên) chuỗi dài nhất trong hai chuỗi, LCS(R1, C0) và LCS (R0, C1). Theo bảng, cả hai đều trống, vì vậy LCS (R1, C1) cũng trống. Các mũi tên biểu thị chuỗi nhập vào: chuỗi đến từ ô ở trên, LCS (R0, C1) và chuỗi đến từ ô ở bên trái, LCS(R1, C0).

LCS (R1, C2) được xác định bằng cách so sánh G và G. Chúng khớp với nhau, nên G được nối vào chuỗi phía trên bên trái, LCS(R0, C1), là (Ø), cho (ØG), ta được (G).

Đối với LCS (R1, C3), G và C không khớp. Chuỗi trên trống; Chuỗi bên trái chứa một phần tử, (G). Chọn phần tử có độ dài dài nhất trong hai chuỗi này, ta được LCS (R1, C3) là (G). Mũi tên chỉ sang trái, vì đó là chuỗi dài nhất trong hai chuỗi.

Tương tự như vậy, LCS(R1, C4) và LCS(R1, C5) là (G).

Hoàn thành hàng "G"
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} Ø	↖ {\displaystyle {\overset {\nwarrow }{\ }}} (G)	← {\displaystyle {\overset {\ }{\leftarrow }}} (G)	← {\displaystyle {\overset {\ }{\leftarrow }}} (G)	← {\displaystyle {\overset {\ }{\leftarrow }}} (G)
A	Ø
C	Ø

Tương tự như vậy, ta hoàn thành hàng R2

Hoàn thành hàng "G" và hàng "A"
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} Ø	↖ {\displaystyle {\overset {\nwarrow }{\ }}} (G)	← {\displaystyle {\overset {\ }{\leftarrow }}} (G)	← {\displaystyle {\overset {\ }{\leftarrow }}} (G)	← {\displaystyle {\overset {\ }{\leftarrow }}} (G)
A	Ø	↖ {\displaystyle {\overset {\nwarrow }{\ }}} (A)	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} (A) & (G)	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} (A) & (G)	↖ {\displaystyle {\overset {\nwarrow }{\ }}} (GA)	← {\displaystyle {\overset {\ }{\leftarrow }}} (GA)
C	Ø

Bảng hoàn thiện cuối cùng là

Bảng LCS đã hoàn thiện
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} Ø	↖ {\displaystyle {\overset {\nwarrow }{\ }}} (G)	← {\displaystyle {\overset {\ }{\leftarrow }}} (G)	← {\displaystyle {\overset {\ }{\leftarrow }}} (G)	← {\displaystyle {\overset {\ }{\leftarrow }}} (G)
A	Ø	↖ {\displaystyle {\overset {\nwarrow }{\ }}} (A)	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} (A) & (G)	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} (A) & (G)	↖ {\displaystyle {\overset {\nwarrow }{\ }}} (GA)	← {\displaystyle {\overset {\ }{\leftarrow }}} (GA)
C	Ø	↑ {\displaystyle {\overset {\ \uparrow }{\ }}} (A)	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} (A) & (G)	↖ {\displaystyle {\overset {\nwarrow }{\ }}} (AC) & (GC)	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} (AC) & (GC) & (GA)	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} (AC) & (GC) & (GA)

Lưu độ dài, thay vì chuỗi
	A	G	C	A	T
Ø	0	0	0	0	0
G	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 0	↖ {\displaystyle {\overset {\nwarrow }{\ }}} 1	← {\displaystyle {\overset {\ }{\leftarrow }}} 1	← {\displaystyle {\overset {\ }{\leftarrow }}} 1	← {\displaystyle {\overset {\ }{\leftarrow }}} 1
A	↖ {\displaystyle {\overset {\nwarrow }{\ }}} 1	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 1	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 1	↖ {\displaystyle {\overset {\nwarrow }{\ }}} 2	← {\displaystyle {\overset {\ }{\leftarrow }}} 2
C	↑ {\displaystyle {\overset {\ \uparrow }{\ }}} 1	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 1	↖ {\displaystyle {\overset {\nwarrow }{\ }}} 2	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 2	← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 2